package code;


/**
 * @author Clover
 *
 * 2015-4-10
 */
public class Code106 {

	/*
	 * 已知二叉树的后续遍历和中序遍历，构建出二叉树
	 * 递归求解，好写。
	 * 看代码
	 *
	 */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	/*
    	 * 只有一个元素，直接返回自己
    	 */
    	int n=inorder.length;
    	TreeNode p=new TreeNode(postorder[n-1]);
    	
    	if(n==1){
    		return p;
    	}
    	int i;
    	for(i=0;i<n;i++){
    		if(inorder[i]==postorder[n-1])
    			break;
    	}
    	/*
    	 * 构建左子树
    	 */
    	//有左子树
    	if(i>0){
    		int[] leftInorder=new int[i];
    		int[] leftPostorder=new int[i];
    		for(int j=0;j<i;j++){
    			leftInorder[j]=inorder[j];
    			leftPostorder[j]=postorder[j];
    		}
    		p.left=buildTree(leftInorder,leftPostorder);
    	}
    	/*
    	 * 构建右子树
    	 * 如果存在右子树的话
    	 */
    	if(i<n-1){
    		int[] rightInorder=new int[n-i-1];
    		int[] rightPostorder=new int[n-i-1];
    		for(int j=i+1;j<n;j++){
    			rightInorder[j-i-1]=inorder[j];
    			rightPostorder[j-i-1]=postorder[j-1];
    		}
    		p.right=buildTree(rightInorder,rightPostorder);
    	}
		return p;
    }
    
    public void dfs(TreeNode p){
    	System.out.println(p.val);
    	if(p.left!=null)
    		dfs(p.left);
    	if(p.right!=null)
    		dfs(p.right);
    }
    public static void main(String[] args){
    	Code106 code=new Code106();
    	int[] postorder={4,5,2,6,7,3,1};
    	int[] inorder={4,2,5,1,6,3,7};
//    	int[] postorder={4,5,2};
//    	int[] inorder={4,2,5};
    	TreeNode root=code.buildTree(inorder, postorder);
    	code.dfs(root);
    }
    
}
